package com.haidechizi.tree.balance;

public class Node {

    int value;

    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    public void addNode(Node node) {
        if (this.value > node.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.addNode(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.addNode(node);
            }
        }

        // 左左向右旋转
        if (leftHeight() - rightHeight() >= 2) {
            if (left != null && left.leftHeight() < left.rightHeight()) {
                left.leftRotate();
            }
            rightRotate();
        }
        if (rightHeight() - leftHeight() >= 2) {
            if (right != null && right.leftHeight() > right.rightHeight()) {
                right.rightRotate();
            }

            leftRotate();
        }

    }

    private void leftRotate() {
        // 创建一个新的节点，将值设置为当前节点的值
        Node newNode = new Node(value);

        // 将当前节点的左子节点设置为新节点的左子节点
        newNode.left = this.left;

        // 将新节点的右子节点的值设置为当前节点的右子节点的左子节点
        newNode.right = this.right.left;

        // 将当前节点的值替换为当前节点的右子节点的值
        value = right.value;

        // 将当前节点的右子节点只设置当前节点的右子节点的右子节点
        right = right.right;
        // 将当亲节点的左子节点设置为新的节点
        left = newNode;
    }

    private void rightRotate() {
        // 创建一个节点，和当前节点的值一样
        Node newNode = new Node(this.value);
        // 把新节点的右子树设置为当前节点的右子树
        newNode.right = this.right;

        // 将当前节点左子树的右子树设置为新及诶单那的左子树
        newNode.left = this.left.right;
        // 将当前节点的值替换为当前节点的左子树的值
        this.value = this.left.value;
        // 将当前及诶单的左子树设置为当前节点的左子树的左子树
        left = left.left;

        // 将新的节点设置为当前节点的右子树
        this.right = newNode;


    }

    public int leftHeight() {
        if (left == null) {
            return 0;
        }
        return left.height();
    }

    public int rightHeight() {
        if (right == null) {
            return 0;
        }
        return right.height();
    }

    public int height() {
        return Math.max(left == null ? 0 : this.left.height(), right == null ? 0 : this.right.height()) + 1;
    }

    public void midShow() {
        if (this.left != null) {
            this.left.midShow();
        }
        System.out.println(this.value);
        if (this.right != null) {
            this.right.midShow();
        }
    }

    public Node searchNode(int value) {
        if (this.value == value) {
            return this;
        }
        if (this.value > value) {
            if (this.left != null) {
                return this.left.searchNode(value);
            }
            return null;
        } else {
            if (this.right != null) {
                return this.right.searchNode(value);
            }
            return null;
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                ", left=" + left +
                ", right=" + right +
                '}';
    }

    public Node searchParent(int i) {
        // 找左子树
        if (this.value > i) {
            if (this.left == null) {
                return null;
            }
            if (this.left.value == i) {
                return this;
            }
            return this.left.searchParent(i);
        } else {
            if (this.right == null) {
                return null;
            }
            if (this.right.value == i) {
                return this;
            }
            return this.right.searchParent(i);
        }
    }
}
